#include<stdio.h>
#include<malloc.h>
/*#include<math.h>*/
#define PARENT(i) (i/2)
#define LEFT(i) (2*(i + 1) - 1)
#define RIGHT(i) (2*(i + 1))
/* Implementing Max-Heap */

typedef struct maxheap MaxHeap;

struct maxheap{
	int *arr;
	int heapsize;
	int capacity;
};

MaxHeap *CreateHeap(int);
int isMaxHeapEmpty(MaxHeap *);
int isMaxHeapFull(MaxHeap *);
int MaxHeapBuild(MaxHeap *, int *, int);
int MaxHeapInsert(MaxHeap *, int);
int MaxHeapMaximum(MaxHeap *);
int MaxHeapExtractMax(MaxHeap *);
void MaxHeapify(MaxHeap *, int);
int *MaxHeapSort(MaxHeap *);

void debug(MaxHeap *);

int power(int x, int y){ //utility function for debug
	int d = x;
	if(y == 0)
		return 1;
	for(; y > 1; y--)
		d = d * x;
	return d;
}

int main(){
	MaxHeap *mh;
	mh = CreateHeap(7);
	int array[] = {1,2,3,4,5,6,7}, i, *ar;
	// build maxheap
	printf("\nBuilding Heap...%s", MaxHeapBuild(mh, array, 7)?"Successful":"Failed");
	//printf("\n\t 2 to the power 4 is %d", power(2, 10));
	debug(mh);
	
	printf("\nHeapsorting...\n");
	ar = MaxHeapSort(mh);
	for(i = 0; i < 7; i++){
		printf("%d\t", ar[i]);
	}
	printf("\n--MaxHeap Operations--\n");
	return 0;
}

MaxHeap *CreateHeap(int cap){
	MaxHeap *MH = (MaxHeap *)malloc(sizeof(MaxHeap));
	if(!MH){
		return NULL;
	}
	MH->arr = (int *)malloc(sizeof(int) * cap);
	if(!MH->arr){
		free(MH);
		return NULL;
	}
	MH->capacity = cap;
	MH->heapsize = 0;
}

int isMaxHeapEmpty(MaxHeap *MH){
	return (MH->heapsize == 0);
}

int isMaxHeapFull(MaxHeap *MH){
	return (MH->heapsize == MH->capacity);
}

int MaxHeapBuild(MaxHeap *MH, int *ar, int n){
	int i = 0;
	if(!MH->arr){
		return 0;
	}
	for(i = 0; i < n && i < MH->capacity; i++){
		MH->arr[i] = ar[i];
	}
	MH->heapsize = i;
	printf("\nHeapifying...\n");
	printf("\nHeapsize is %d", MH->heapsize);
	for(i = (MH->heapsize/2)-1; i >= 0; i--){
		printf("\nHeapifying at %d and the value here is: %d", i, MH->arr[i]);
		MaxHeapify(MH, i);
	}
	return 1;
}	

int MaxHeapInsert(MaxHeap *MH, int data){
	if(isMaxHeapFull(MH)){
		return 0;
	}else{
		// todo
		return 1;
	}
}

int MaxHeapMaximum(MaxHeap *MH){
	return MH->arr[0];
}

int MaxHeapExtractMax(MaxHeap *MH){
	if(isMaxHeapEmpty(MH)){
		return 0;
	}
	int data = MH->arr[0];
	MH->arr[0] = MH->arr[MH->heapsize-1];
	MH->heapsize = MH->heapsize - 1;
	MaxHeapify(MH, 0);
	return data;
}

void MaxHeapify(MaxHeap *MH, int pos){
	int left = LEFT(pos), right = RIGHT(pos), largest = pos;
	printf("\nleft is: %d and right is: %d", left, right);
	if(left < MH->heapsize && MH->arr[left] > MH->arr[pos]){
		largest = left;
	}
	if(right < MH->heapsize && MH->arr[right] > MH->arr[largest]){
		largest = right;
	}
	if(largest != pos){
		int temp = MH->arr[largest];
		MH->arr[largest] = MH->arr[pos];
		MH->arr[pos] = temp;
		MaxHeapify(MH, largest);
	}
}

int *MaxHeapSort(MaxHeap *MHprev){
	MaxHeap *MH = CreateHeap(MHprev->heapsize);
	int i = 0, temp;
	if(!MH){
		return NULL;
	}
	MaxHeapBuild(MH, MHprev->arr, MHprev->heapsize);
	debug(MH);
	while(MH->heapsize > 1){
		printf("\nMH heapsize: %d\tMax element: %d\tlast element now: %d", MH->heapsize, MH->arr[0], MH->arr[MH->heapsize-1]);
		debug(MH);
		temp = MH->arr[0];
		MH->arr[0] = MH->arr[MH->heapsize - 1];
		MH->arr[MH->heapsize - 1] = temp;
		MH->heapsize = MH->heapsize - 1;
		MaxHeapify(MH, 0);
	}
	MH->heapsize = MHprev->heapsize;
	debug(MH);
	/*int *ar = (int *)malloc(sizeof(int) * MHprev->heapsize);
	for(i = 0; i < MHprev->heapsize; i++){
		ar[i] = MH->arr[i];
	}
	free(MH->arr);
	free(MH);*/
	return MH->arr;
}

void debug(MaxHeap *MH){
	printf("\n--DEBUG--\n");
	int i = 0, height = 0;
	for(i = 0; i < (MH->heapsize); i++){
		printf("%d\t", MH->arr[i]);
		if((i+1) == (power(2,height+1) - 1)){
			printf("\n");
			height++;
		}
	}
	printf("\n--DEBUG--\n");
}
